'''
https://leetcode.cn/problems/coin-change/
'''
from typing import List


'''
公式： f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1
    之所以最后+1，是因为要先拿一块硬币，再计算剩余面额怎么用硬币组合
例： 
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
f(11) = min(f(10), f(9), f(6)) + 1
'''
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        # res = [0 for _ in range(amount + 1)]
        res = [0]*(amount + 1)

        for i in range(1, amount + 1):
            cost = float('inf')
            for c in coins:
                if i - c >= 0:
                    cost = min(cost, res[i - c] + 1)
            res[i] = cost

        if res[amount] == float('inf'):
            return -1
        else:
            return res[amount]

s = Solution()
coins = [1, 2, 5]
amount = 11
print(s.coinChange(coins, amount))

'''
求面值amount用coins一共可以给出多少种组合数
https://leetcode.cn/problems/coin-change-ii/
'''
#-----------------------------------------------------------
class Solution002:
    def change(self, amount: int, coins: List[int]) -> int:
        if amount == 0: return 0
        dp = [0]*(amount + 1)
        dp[0] = 1 # 当面值与硬币值相等的时候，那么使用这个硬币就只有1种组合 # 0用0的组合就只有1种
        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1): # 面值
                # dp[j] 表示组成面值j共有dp[j]种组合数
                # dp[j - coins[i]] 表示组成面值j - coins[i]的组合数
                # 用 += 号，是因为每次遍历，d[j]都会记录当前coins[i]的组合数，加起来才是总得组合数
                dp[j] += dp[j - coins[i]]
        return dp[amount]

amount = 4
coins = [1, 2]
s = Solution002()

res = s.change(amount, coins)
print(res)










